package leetcode_周赛._2022._202209;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 第 312 场周赛
 *
 * @author yzh
 * @version 1.0
 * @date 2022/9/30 12:21
 */
public class _25 {

    /**
     * 2419. 按位与最大的最长子数组
     * 算法：脑筋急转弯
     * 与只会越来越小, 只需找到 nums 中最大的那个数即可
     *
     * @param nums nums
     * @return num
     */
    public int longestSubarray(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int num : nums) max = Math.max(max, num);
        int ans = 0, n = nums.length;
        for (int i = 0; i < n; ) {
            if (nums[i] == max) {
                int j = i + 1;
                while (j < n && nums[j] == max) ++j;
                ans = Math.max(ans, j - i);
                i = j;
            } else ++i;
        }
        return ans;
    }

    /**
     * 2420. 找到所有好下标
     * 算法：动态规划
     *
     * @param nums nums
     * @param k    k
     * @return list
     */
    public List<Integer> goodIndices(int[] nums, int k) {
        int n = nums.length;
        int[] left = new int[n], right = new int[n];
        Arrays.fill(left, 1); Arrays.fill(right, 1);
        for (int i = 1; i < n; i++) {
            if (nums[i] <= nums[i - 1]) left[i] = left[i - 1] + 1;
            if (nums[i] >= nums[i - 1]) right[i] = right[i - 1] + 1;
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = k; i < n - k; i++) if (left[i - 1] >= k && right[i + k] >= k) ans.add(i);
        return ans;
    }

}
